from tools_algorithm import *


class Solution:
    def lastNonEmptyString(self, s: str) -> str:
        h = Counter()
        for v in s:
            h[v] += 1
        mx = max(h.values())
        d = {}
        for i, v in enumerate(s):
            if h[v] == mx:
                d[v] = i
        s = sorted(d.keys(), key=lambda k: d[k])
        return "".join(s)


class Solution:

    def maxOperations(self, nums: List[int]) -> int:
        @cache
        def f(l, r, num):
            if l >= r:
                return 0
            ans = 0
            if nums[l] + nums[l + 1] == num:
                ans = max(ans, f(l + 2, r, num) + 1)
            if nums[l] + nums[r] == num:
                ans = max(ans, f(l + 1, r - 1, num) + 1)
            if nums[r] + nums[r - 1] == num:
                ans = max(ans, f(l, r - 2, num) + 1)
            return ans

        def g(num):
            return f(0, len(nums) - 1, num)

        return max(g(nums[0] + nums[-1]), g(nums[-1] + nums[-2]), g(nums[0] + nums[1]))


s = Solution()
print(s.maxOperations([3, 2, 1, 2, 3, 4]))
